Big O notation untuk mengukur efisiensi algoritma menunjukkan bagaimana kebutuhan waktu atau memori sebuah program tumbuh ketika jumlah data bertambah. Kalau kamu sudah bisa menulis kode yang berjalan benar, langkah berikutnya adalah menilai apakah kode itu tetap layak dipakai saat datanya membesar. Big O memberi bahasa untuk menjawab pertanyaan itu tanpa harus menjalankan program di tiap ukuran data.
Apa yang sebenarnya diukur Big O
Big O tidak mengukur waktu dalam satuan detik. Angka detik bergantung pada kecepatan CPU, bahasa pemrograman, dan beban sistem yang berbeda-beda di setiap mesin. Yang diukur adalah jumlah langkah operasi sebagai fungsi dari ukuran input, biasanya dilambangkan n.
Karena itu, algoritma dengan kompleksitas O(n) berarti jumlah operasinya tumbuh sebanding dengan banyaknya data. Kalau data berlipat dua, operasinya kira-kira berlipat dua juga. Algoritma O(n²) membuat operasi membengkak menjadi empat kali lipat ketika data berlipat dua.
Big O juga membuang konstanta dan suku yang lebih kecil. Algoritma yang menjalankan 3n + 50 operasi tetap ditulis O(n). Ketika n sangat besar, suku 3n mendominasi dan angka 50 tidak lagi berpengaruh berarti.
Jenis kompleksitas yang sering muncul
Sebagian besar kode yang kamu tulis sehari-hari akan jatuh ke salah satu dari beberapa kelas berikut.
| Notasi | Nama | Contoh kasus |
|---|---|---|
| O(1) | Konstan | Mengakses elemen array lewat indeks |
| O(log n) | Logaritmik | Binary search pada data terurut |
| O(n) | Linear | Menelusuri seluruh isi array sekali |
| O(n log n) | Linearitmik | Merge sort, quick sort rata-rata |
| O(n²) | Kuadratik | Loop bersarang untuk membandingkan semua pasangan |
| O(2ⁿ) | Eksponensial | Menghitung kombinasi dengan rekursi tanpa memoisasi |
Urutan dari yang paling ringan ke paling berat adalah O(1), O(log n), O(n), O(n log n), O(n²), lalu O(2ⁿ). Perbedaan antara O(n) dan O(n²) baru terasa ketika data mencapai puluhan ribu baris atau lebih.
Membaca Big O dari kode
Kamu bisa memperkirakan kompleksitas dengan menghitung seberapa dalam loop bersarang dan seberapa banyak data yang disentuh di dalamnya. Satu loop yang menelusuri n elemen berarti O(n). Dua loop bersarang yang masing-masing menelusuri n elemen berarti O(n²).
def cari_pasangan_duplikat(data):
hasil = []
for i in range(len(data)):
for j in range(i + 1, len(data)):
if data[i] == data[j]:
hasil.append((data[i], data[j]))
return hasil
Fungsi di atas membandingkan setiap pasangan elemen, sehingga operasinya kira-kira n(n-1)/2 dan masuk kategori O(n²). Untuk 10.000 data, itu berarti puluhan juta perbandingan. Menggantinya dengan set yang menyimpan elemen yang sudah dilihat bisa menurunkan kompleksitas menjadi O(n).
Perhatikan juga operasi tersembunyi. Memanggil in pada list di Python memakan waktu O(n) karena Python memeriksa elemen satu per satu. Kalau pemanggilan itu berada di dalam loop, totalnya menjadi O(n²) meskipun kode terlihat hanya punya satu loop. Memilih struktur data yang tepat sering kali lebih menentukan daripada menulis ulang logikanya.
Untuk algoritma rekursif, kompleksitas dihitung dari berapa kali fungsi memanggil dirinya sendiri dan berapa besar data yang diproses di setiap panggilan. Binary search membagi data menjadi dua setiap kali, sehingga kedalamannya sekitar log₂ n dan kompleksitasnya O(log n).
Kapan efisiensi algoritma benar-benar penting
Menilai kompleksitas bukan berarti semua kode harus O(1). Untuk data kecil, algoritma O(n²) sering kali lebih cepat dalam praktik karena lebih sedikit overhead dibanding algoritma O(n log n) yang punya banyak operasi tambahan per langkah.
Masalahnya muncul ketika data tumbuh. Pencarian linear pada 100 elemen tidak akan terasa. Pencarian linear yang dipanggil ribuan kali pada data berisi ratusan ribu baris bisa membuat halaman web tertahan beberapa detik. Di titik itulah analisis Big O berguna, karena kamu bisa memperkirakan dampaknya sebelum pengguna mengeluh.
Memahami pola ini juga membantu saat memilih pendekatan. Kalau kamu tahu bahwa pencarian berulang pada data terurut bisa memakai binary search, kamu tidak perlu menebak-nebak. Kebiasaan semacam ini terbentuk dari latihan rutin, misalnya lewat latihan logika algoritma dengan soal harian yang memaksamu memikirkan batasan waktu sebelum menulis kode.
Kesalahan umum saat menilai kompleksitas
- Menganggap semua loop bersarang pasti O(n²). Kalau loop dalam hanya berjalan sejumlah konstanta langkah, totalnya tetap O(n).
- Mengabaikan biaya operasi bawaan bahasa. Penyambungan string berulang di dalam loop bisa berujung O(n²) meski terlihat sederhana.
- Fokus pada waktu tapi melupakan memori. Algoritma yang cepat bisa memakan ruang besar, dan itu juga punya batas.
- Membandingkan dua algoritma hanya dari notasi Big O tanpa menguji pada data nyata yang ukurannya realistis.
Kesalahan lain yang sering muncul adalah menulis kode berdasarkan pseudocode tanpa memeriksa kompleksitasnya. Saat membaca pseudocode dari buku atau referensi, biasakan mencatat berapa banyak loop dan bagaimana data diproses. Panduan membaca pseudocode algoritma membantu memisahkan langkah inti dari detail yang tidak memengaruhi kompleksitas.
Melatih kebiasaan menghitung kompleksitas
Setelah menyelesaikan sebuah fungsi, tanyakan dua hal: berapa kali fungsi itu menyentuh data, dan apakah ada operasi yang lebih mahal dari yang terlihat. Catat jawabannya dalam satu baris komentar di atas fungsi. Kebiasaan kecil ini membuatmu lebih cepat mengenali bagian kode yang berpotensi melambat.
Untuk tugas yang lebih besar, misalnya membangun dashboard dengan tabel data panjang, keputusan struktur data berhubungan langsung dengan pengalaman pengguna. Artikel tentang metode riset pengguna untuk desain antarmuka menunjukkan bagaimana data dari pengguna bisa memandu keputusan teknis semacam ini. Di sisi tampilan, teknik seperti merapikan tampilan tabel data dengan jQuery juga perlu mempertimbangkan berapa banyak baris yang dirender agar halaman tetap responsif.
Untuk algoritma yang lebih rumit, mulailah dari versi sederhana, ukur pertumbuhannya, lalu pertimbangkan optimasi. Mengukur dulu mencegah kamu mengoptimasi bagian yang bukan penyebab lambat. Pola pikir ini sejalan dengan menghindari kesalahan umum dalam menerapkan algoritma.
Ringkasan
Big O notation menjelaskan pertumbuhan kebutuhan waktu atau memori suatu algoritma saat ukuran data bertambah. Nilai kompleksitas dibaca dengan menghitung loop, operasi berulang, dan kedalaman rekursi, lalu membuang konstanta. Gunakan analisis ini untuk memilih struktur data dan memperkirakan titik di mana kode mulai melambat, bukan sebagai patokan mutlak untuk setiap fungsi.
Pertanyaan yang Sering Diajukan
Apakah algoritma O(n²) selalu buruk?
Tidak. Untuk data berukuran kecil, O(n²) sering kali lebih cepat karena overhead-nya rendah. Masalahnya baru muncul ketika data bertambah besar dan jumlah operasinya melonjak.
Bagaimana cara menghitung Big O pada fungsi rekursif?
Hitung berapa kali fungsi memanggil dirinya sendiri dan berapa besar data yang diproses di setiap panggilan. Binary search memanggil dirinya satu kali dengan data setengah ukuran, sehingga kompleksitasnya O(log n), sementara rekursi Fibonacci tanpa memoisasi bercabang dua setiap langkah dan masuk O(2ⁿ).
Apakah Big O memperhitungkan kecepatan bahasa pemrograman?
Tidak. Big O hanya menggambarkan pola pertumbuhan operasi, bukan waktu eksekusi nyata. Bahasa dan mesin yang berbeda akan memberi angka detik berbeda, tetapi urutan pertumbuhannya tetap sama.